package algorithms.leecode;

public class Au67 {
    public static void main(String[] args) {
        System.err.println(new Au67().addBinary("1","0"));
    }
    public String addBinary(String a, String b) {
        int len = Math.max(a.length(),b.length());
        String out = a.length ()== len? a : b;
        String in = a.length() == len ? b : a;
        int inMaxIndex = in.length() - 1;
        int outMaxIndex = len - 1;
        char[] res1 = new char[len+1];
        char[] res2 = out.toCharArray();
        boolean add = false;
        while(outMaxIndex >= 0) {
            // 最后一位
            if(outMaxIndex == 0) {
                if(out.charAt(outMaxIndex) == '1') {
                    if(inMaxIndex >=0 ) {
                        if(in.charAt(inMaxIndex) == '1' && add) {
                            res1[1] = '1';
                        }
                        if(in.charAt(inMaxIndex) == '1' && !add) {
                            res1[1] = '0';
                        }
                        if(in.charAt(inMaxIndex) == '0' && !add) {
                            return new String(res2);
                        }
                        if(in.charAt(inMaxIndex) == '0' && add) {
                            res1[1] = '0';
                        }
                    } else {
                        if (add) {
                            res1[1] = '0';
                        } else {
                            return new String(res2);
                        }
                    }
                    res1[0] =  '1';
                    return new String(res1);
                } else{
                    if(inMaxIndex >=0 ) {
                        if(in.charAt(inMaxIndex) == '1' && !add) {
                            res2[0] = '1';
                            return new String(res2);
                        }
                        if(in.charAt(inMaxIndex) == '1' && add) {
                            res1[0] = '1';
                            res1[1] = '0';
                            return new String(res1);
                        }
                    }
                    res2[0] = '0';
                    return new String(res2);
                }
            }
            // 其他
            else{
                if(inMaxIndex >=0) {
                    char inc = in.charAt(inMaxIndex);
                    char ouc = out.charAt(outMaxIndex);
                    if(inc == '1' && ouc == '1') {
                        if (add) {
                            res1[outMaxIndex + 1] = '1';
                            res2[outMaxIndex] = '1';
                        } else {
                            add = true;
                            res1[outMaxIndex + 1] = '0';
                            res2[outMaxIndex] = '0';
                        }
                    }
                    if(inc == '1' && ouc == '0') {
                        if (add) {
                            res1[outMaxIndex + 1] = '0';
                            res2[outMaxIndex] = '0';
                        } else {
                            res1[outMaxIndex + 1] = '1';
                            res2[outMaxIndex] = '1';
                            add = false;
        //                    return new String(res2);
                        }
                    }
                    if(inc == '0' && ouc == '1') {
                        if (add) {
                            res1[outMaxIndex + 1] = '0';
                            res2[outMaxIndex] = '0';
                        } else {

                            res1[outMaxIndex + 1] = '1';
                            res2[outMaxIndex] = '1';
                            add = false;
                //            return new String(res2);
                        }
                    }
                    if(inc == '0' && ouc == '0') {
                        if (add) {
                            res1[outMaxIndex + 1] = '1';
                            res2[outMaxIndex] = '1';
                            add = false;
          //                  return new String(res2);
                        } else {
                            res1[outMaxIndex + 1] = '0';
                            res2[outMaxIndex] = '0';
                            add = false;
             //               return new String(res2);
                        }
                    }
                } else {
                    char ouc = out.charAt(outMaxIndex);
                    if (ouc == '1') {
                        if (add) {
                            res1[outMaxIndex + 1] = '0';
                            res2[outMaxIndex] = '0';
                        } else {
                            res1[outMaxIndex + 1] = '1';
                            res2[outMaxIndex] = '1';
                            return new String(res2);
                        }
                    } else {
                        if (add) {
                            res1[outMaxIndex + 1] = '1';
                            res2[outMaxIndex] = '1';
                        }
                        return new String(res2);
                    }
                }
            }

            outMaxIndex--;
            inMaxIndex--;
        }
return b;
    }
}
